package bite;

import java.util.Scanner;

/**
 * Creared with IntelliJ IDEA.
 * Description:【最长公共子序列】我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
 * 例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
 * 现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。
 * User:yxd
 * Date:2022-06-18
 * Time:17:58
 */
public class Day39_1 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){

            String str = input.next();
            String sub = input.next();
            int n = str.length();
            int m = sub.length();
            //状态定义 F(i,j)表示前i个字符和前j个字符的公共子串长度
            //状态转移方程F(i,j) 如果当前字符相等就看i-1,j-1不相等就从i-1,j和i,j-1中取最大值
            //赋初值第一行和第一列都是0
            int[][] dp = new int[n + 1][m + 1];
            for(int i = 0;i <= n;i ++){
                dp[i][0] = 0;
            }
            for(int j = 0;j <= m;j ++){
                dp[0][j] = 0;
            }
            for(int i = 1;i <= n;i ++){
                for (int j = 1; j <= m; j++) {
                    if(str.charAt(i - 1) == sub.charAt(j - 1)){
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }else{
                        dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    }
}
